package special;

import java.util.*;

public class LeeCode_LCP_41 {
    public static void main(String[] args) {
        System.out.println(flipChess(new String[]{"....X.", "....X.", "XOOO..", "......", "......"}));
    }
    private static int flipChess(String[] chessboard) {
        int m = chessboard.length, n = chessboard[0].length();
        char[][] cs = new char[m][n];
        for (int i = 0; i < m; i++) {
            cs[i] = chessboard[i].toCharArray();
        }
        int ans = 0;
        int[][] dirs = new int[][]{{0,1},{0,-1},{1,0},{-1,0},{-1,-1},{-1,1},{1,-1},{1,1}};
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (cs[i][j] == '.'){
                    char[][] copy = new char[m][n];
                    for (int k = 0; k < m; k++) {
                        copy[k] = Arrays.copyOfRange(cs[k], 0, n);
                    }
                    copy[i][j] = 'X';
                    ans = Math.max(ans, bfs(copy, dirs, i, j));
                }
            }
        }
        return ans;
    }
    private static int bfs(char[][] cs, int[][] dirs, int i, int j){
        int m = cs.length, n = cs[0].length;
        Deque<int[]> deque = new ArrayDeque<>();
        deque.add(new int[]{i, j});
        int res = 0;
        while (!deque.isEmpty()){
            int[] p = deque.pop();
            int x = p[0], y = p[1];
            for (int[] dir : dirs) {
                int ax = dir[0], ay = dir[1], tx = x, ty = y;
                LinkedList<int[]> queue = new LinkedList<>();
                tx += ax;
                ty += ay;
                while (tx >= 0 && tx < m && ty >= 0 && ty < n){
                    queue.add(new int[]{tx, ty});
                    if (cs[tx][ty] != 'O'){
                        break;
                    }
                    tx += ax;
                    ty += ay;
                }
                if (queue.size() == 0)
                    continue;
                int[] t = queue.pollLast();
                if (cs[t[0]][t[1]] == 'X'){
                    res += queue.size();
                    while (!queue.isEmpty()){
                        int[] tp = queue.pollFirst();
                        cs[tp[0]][tp[1]] = 'X';
                        deque.add(tp);
                    }
                }
            }
        }
        return res;
    }
}